﻿using System;
using System.Collections.Generic;
using System.Text;
using System.Linq;

namespace AlgorithmTest
{
    // T_[四个数字排序]_[算法名]
    public class T_0179_PathSum : IAlgorithm
    {
        // 113. 路径总和 II

        // 给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。

        // 叶子节点 是指没有子节点的节点。

        // 提示：
        //  树中节点总数在范围[0, 5000] 内
        //  -1000 <= Node.val <= 1000
        //  -1000 <= targetSum <= 1000

        public void Test()
        {
            // 算法参数定义

            // 算法执行与打印
            //Console.WriteLine(Algorithm());
            //var res = Algorithm(param);
            //foreach (var item in res)
            //{
            //    foreach (var iitem in item)
            //    {
            //        Console.Write(iitem + " ");
            //    }
            //    Console.WriteLine();
            //}
        }

        // 算法

        List<IList<int>> ret = new List<IList<int>>();
        Stack<int> path = new Stack<int>();

        public IList<IList<int>> PathSum(TreeNode root, int targetSum)
        {
            Dfs(root, targetSum);
            return ret;
        }

        public void Dfs(TreeNode root, int targetSum)
        {
            if (root == null)
            {
                return;
            }
            path.Push(root.val);
            targetSum -= root.val;
            if (root.left == null && root.right == null && targetSum == 0)
            {
                var ans = path.ToList();
                ans.Reverse();
                ret.Add(ans);
            }
            Dfs(root.left, targetSum);
            Dfs(root.right, targetSum);
            path.Pop();
        }


    }
}
